#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 115. 不同的子序列
    // https://leetcode.cn/problems/distinct-subsequences/
    int numDistinct(string s, string t) {
        static const int MOD = 1e9 + 7;
        int n1 = s.size(), n2 = t.size();

        vector<vector<int>> dp(n1+1, vector<int>(n2+1));
        s = ' ' + s;
        t = ' ' + t;

        for (int i = 0; i<=n1; ++i)
            dp[i][0] = 1;
        
        for (int i = 1; i<=n1; ++i)
        {
            for (int j = 1; j<=n2; ++j)
            {
                dp[i][j] = (dp[i-1][j] + (s[i] == t[j] ? dp[i-1][j-1] : 0)) % MOD;
            }
        }

        return dp[n1][n2];
    }
};